package com.redstar.day03_sushutongji;

/**
 * 题目：统计n以内的素数的个数
 * 素数：除了 0 和 1 以外，只能被 1 和它自身整除的自然数
 * 输入一个数(如 100),返回这个数以内素数的个数(25个)
 *
 * @author lihongxing
 * @date 2021/04/21 00:15
 */
public class Test {


    /**
     * 方法一：暴力法
     * 输入n，暴力法，逐个判断n以内的每个数是否是素数，如果是，则计数器+1
     */
    private static int firstMethod(int n) {
        int count = 0;
        for (int i = 2; i < n; i++) {
            count += isPrime(i) ? 1 : 0;
        }
        return count;
    }

    /**
     * 判断这个数是否是素数
     * 将这个数x与从2开始到x-1逐个相除来判断这个数是否是素数,如果x被 2至x-1中的某个数除断，则说明不是素数
     * 优化一：将 i<x 改为 i * i <= x
     */
    private static boolean isPrime(int x) {
        for (int i = 2; i * i <= x; i++) {
            if ((x % i) == 0) {
                return false;
            }
        }
        return true;
    }


    /**
     * 方法二：埃筛法
     * 一个素数 和 大于1 的任何数相乘 得到的数就是非素数
     * 因此，每当我们找到一个素数的时候，我们就对这个素数进行倍增，那么这些倍增的数就是非素数，后面就可以直接跳过
     */
    private static int secondMethod(Integer n) {
        //标记位，初始化，数组中全部都是false。默认 false 代表素数
        boolean[] is = new boolean[n];
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (!is[i]) {
                count++;
                //j就是合数的标记位
                for (int j = 2 * i; j < n; j += i) {
                    is[j] = true;
                }
            }
        }
        return count;
    }


    public static void main(String[] args) {
        long l = System.currentTimeMillis();
        System.out.println(firstMethod(1000000) + "个,耗时：" + (System.currentTimeMillis() - l));

        long l1 = System.currentTimeMillis();
        System.out.println(secondMethod(1000000) + "个,耗时：" + (System.currentTimeMillis() - l1));

    }

}
